#include<iostream>
#include<vector>
using namespace std;

//1137.第N个泰波纳契数列
//状态表示
long dp[38];
int tribonacci(int n){
    //初始化
    dp[0] = 0, dp[1] = 1, dp[2] = 1;

    //填表
    for (int i = 3; i <= n;i++){
        //状态转移方程
        dp[i] = dp[i - 3] + dp[i - 2] + dp[i - 1];
    }

    //返回值
    return dp[n];
}
//空间优化
long dp[3];
int tribonacci(int n){
    dp[0] = 0, dp[1] = 1, dp[2] = 1;

    for (int i = 3; i <= n;i++){
        //滚动数组优化空间复杂度
        dp[i % 3] = dp[0] + dp[1] + dp[2];
    }

    return dp[n % 3];
}


//面试题.三步问题
int waysToStep(int n){
    long long dp[1000001];

    //初始化
    dp[0] = 1, dp[1] = 1, dp[2] = 2;

    //填表
    for (int i = 3; i <= n;i++){
        //状态转移方程
        dp[i] = (dp[i - 1] + dp[i - 2] + dp[i - 3]) % 1000000007;
    }

    //返回值
    return dp[n];
}
//滚动数组优化
//状态表示
int waysToStep(int n){
    long long dp[3];
    //初始化
    dp[0] = 1, dp[1] = 1, dp[2] = 2;

    //填表
    for (int i = 3; i <= n;i++){
        //状态转移方程
        dp[i % 3] = (dp[0] + dp[1] + dp[2]) % 1000000007;
    }

    //返回值
    return dp[n % 3];
}


//746.使用最小花费爬楼梯
//方式一：
int minCostClimbingStairs(vector<int>& cost){
    int n = cost.size();
    //状态表示，dp[i]表示以i为终点，到达i位置的最小花费
    int dp[1001];

    // 初始化
    dp[0] = dp[1] = 0;

    //从左往右填表
    for (int i = 2; i <= n; i++){
        //状态转移方程
        dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
    }

    //返回值
    return dp[n];
}
//方式二：
int minCostClimbingStairs(vector<int>& cost){
    int n = cost.size();
    //状态表示，dp[i]表示以i为起点，从i位置到达顶点的最小花费
    int dp[n];

    //初始化
    dp[n - 1] = cost[n - 1], dp[n - 2] = cost[n - 2];

    //从右往左填表
    for (int i = n - 3; i >= 0; i--){
        //状态转移方程
        dp[i] = min(dp[i + 1] + cost[i], dp[i + 2] + cost[i]);
    }

    //返回值
    return min(dp[0], dp[1]);
}

//91.解码方法
int numDecodings(string s){
    int n = s.size();
    //状态表示,dp[i]表示以i+1为结尾的解码总数
    int dp[101];

    //初始化
    int x = s[0] - '0', y = s[1] - '0';
    dp[0] = 0;
    if (x >= 1 && x <= 9){
        dp[0] += 1;
    }
    dp[1] = 0;
    //判断两个单独解码是否成功
    if (x >= 1 && x <= 9 && y >= 1 && y <= 9){
        dp[1] += 1;
    }
    //判断两个组合是否解码成功
    if (x * 10 + y >= 10 && x * 10 + y <= 26){
        dp[1] += 1;
    }

    //填表，从左往右
    for (int i = 2; i < n; i++){
        x = s[i - 1] - '0', y = s[i] - '0';

        dp[i] = 0;
        //判断i位置单独解码是否成功
        if (y >= 1 && y <= 9){
            //找i-1位置结尾的解码总数
            dp[i] += dp[i - 1];
        }
        //判断i位置和i-1位置组合解码是否成功
        if (x * 10 + y >= 10 && x * 10 + y <= 26){
            //找i-2位置结尾的解码总数
            dp[i] += dp[i - 2];
        }
    }

    return dp[n - 1];
}
//优化
int numDecodings(string s){
    int n = s.size();
    //状态表示,dp[i]表示以i为结尾的解码总数
    int dp[n + 1];

    //初始化
    dp[0] = 1;
    dp[1] = 0;
    if(s[0]>='0'&&s[0]<='9'){
        dp[1] += 1;
    }

    for (int i = 2; i <= n; i++){
        //下标映射
        int x = s[i - 2] - '0', y = s[i - 1] - '0';

        dp[i] = 0;
        if (y >= 1 && y <= 9){
            dp[i] += dp[i - 1];
        }
        if (x * 10 + y >= 10 && x * 10 + y <= 26){
            dp[i] += dp[i - 2];
        }
    }

    return dp[n];
}

int main(){

    return 0;
}